package cn.dglydrpy.study.algorithm.od;

import java.util.*;

/**
 * @author Yyy
 * @date 2024/11/6 11:46
 * @description
 * 题目描述：给定一个 32 位正整数，进行因数分解找到两个素数之积，若找不到则输出 - 1 -1。
 */
public class Od0011_MuiltiPrime {
    public static void main(String[] args) {
//        int num = 27;

        // 交互式验证
//        Scanner scanner = new Scanner(System.in);
//        while(scanner.hasNextInt()){
//            int num = scanner.nextInt();
//            System.out.println(myAnswer(num));
//            System.out.println(answer1(num));
//        }
        
        // 对数器验证
        boolean succeed = true;
        for(int i=0;i<=Integer.MAX_VALUE;i++){

            System.out.println("num：" + i);

            long start = System.currentTimeMillis();
            String myAnswer = myAnswer(i);
            long end = System.currentTimeMillis();
            System.out.println("myAnswer耗时：" + (end - start));

            start = System.currentTimeMillis();
            String answer1 = answer1(i);
            end = System.currentTimeMillis();
            System.out.println("answer1耗时：" + (end - start));

            if(!myAnswer.equals(answer1)){
                System.out.println("myAnswer:" + myAnswer);
                System.out.println("answer1:" + answer1);
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
  
    }

    private static String myAnswer(int num) {
        StringBuilder ans = new StringBuilder();
        if(num <= 3 || isPrime(num)){
            ans.append("-1 -1");
            return ans.toString();
        }

        ArrayList<Integer> primes = primeList(num);
        int max = (int) Math.sqrt(num); 
        for(int i = 0;i<max + 1;i++){
            if(num % primes.get(i) != 0){continue;}
            int target = num/primes.get(i);
            for(int j = i; j<primes.size();j++){
                if(primes.get(j) == target){
                    ans.append(primes.get(i)).append(" ").append(primes.get(j));
                    return ans.toString();
                }
                if(primes.get(j) > target){
                    break;
                }
            }
        }
        ans.append("-1 -1");
        return ans.toString();
    }
    
    private static ArrayList<Integer> primeList(int num){

        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0;i <= num; i++){
            if(isPrime(i)){
                res.add(i);
            }
        }
      
        return res;
    }

    public static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        }
        if (number == 2 || number == 3) {
            return true;
        }
        if (number % 2 == 0 || number % 3 == 0) {
            return false;
        }
        int i = 5;
        while (i * i <= number) {
            if (number % i == 0 || number % (i + 2) == 0) {
                return false;
            }
            i += 6;
        }
        return true;
    }


    static Set<Integer> set = new HashSet<>();
    public static String answer1(int num) {
        if (num <= 3) {
            return "-1 -1";
        }
        int sq = (int) Math.sqrt(num);
        for (int i = 2; i <= sq; i++) {
            if (num % i != 0) continue;
            if (set.contains(i)) {
                int j = num / i;
                if (set.contains(j)) {
                    return i + " " + j;
                }
                if (check(j)) {
                    return i + " " + j;
                }
            }
            if (check(i)) {
                int j = num / i;
                if (set.contains(j)) {
                    return i + " " + j;
                }
                if (check(j)) {
                    return i + " " + j;
                }
            }
        }
        return "-1 -1";
    }

    public static boolean check(int n) {
        int sq = (int) Math.sqrt(n);
        for (int i = 2; i <= sq; i++) {
            if (n % i == 0) return false;
        }
        set.add(n);
        return true;
    }

}
